package _go

//记录结果值
var res [][]int

func minFallingPathSum(matrix [][]int) int {
	l := len(matrix)
	if l < 0 {
		return 0
	}
	if l == 1 {
		return matrix[0][0]
	}
	res = [][]int{}
	for i := 0; i < l; i++ {
		tmp := []int{}
		for j := 0; j < l; j++ {
			tmp = append(tmp, 666666)
		}
		res = append(res, tmp)
	}

	var r int = 999999
	for i := 0; i < l; i++ {
		tmp := dp(matrix, l-1, i)
		//fmt.Printf("tmp%d\n", tmp)
		if tmp < r && tmp != 999999 {
			r = tmp
		}
	}
	return r
}

func dp(matrix [][]int, i, j int) int {

	if check(matrix, i, j) == false {
		return 999999
	}
	//	fmt.Printf("i :%d j:%d \n", i, j)
	if i == 0 {
		return matrix[0][j]
	}
	if res[i][j] != 666666 {
		return res[i][j]
	}
	res[i][j] = matrix[i][j] + min3(
		dp(matrix, i-1, j-1),
		dp(matrix, i-1, j+1),
		dp(matrix, i-1, j),
	)
	return res[i][j]
}

func min3(i, j, z int) int {
	return min(i, min(j, z))
}
func min(i, j int) int {
	if i > j {
		return j
	} else {
		return i
	}
}

func check(matrix [][]int, i, j int) bool {
	l := len(matrix)

	if i >= l || j >= l || i < 0 || j < 0 {
		return false
	}

	return true
}
